#include<stdio.h>

int main()
{
    int n, a, b, x;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d %d", &a, &b);
        for(int i = 1; i <= b; i ++)
        {
            x *= a;
            x %= 1000;//只有后三位有用
        }
        printf("%d\n", x);
        x = 1;//恢复初始值
    }
    return 0;
}
//这样写数据可能有溢出
// #include<stdio.h>
// #include<math.h>
// int main()
// {
//     int n, a, b;
//     scanf("%d", &n);
//     for(int i = 1; i <= n; i ++)
//     {
//         scanf("%d %d", &a, &b);
//         int x = pow(a,b);
//         printf("%d\n", x%1000);

//     }
//     return 0;
// }